package com.monkeyboy.stack;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 求字符流中第一个不重复的字符
 *  请实现一个函数用来找出字符流中第一个只出现一次的字符。
 *  例如，当从字符流中只读出前两个字符 "go" 时，
 *  第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时，第一个只出现一次的字符是 "l"。
 *
 *  解题思路：
 *      首先是字符流，所以考虑用队列，不重复的字符，字符的ASCII是128个，所以考虑用数组作为标记位
 * @Author Gavin
 * @date 2021.04.01 10:53
 */
public class Stack05 {
    private int[] arr=new int[128];
    private Queue<Character> queue=new LinkedList<>();//注意不能使用PriorityQueue，它是优先级队列，不是先进先出的
    public void insert(char c){
        arr[c]++;
        queue.add(c);
        /**
         * 临界条件分析：
         * 1. 首先要保证队列不为空，然后判断队列的首元素在数组中下标的值是否大于1，大于1则说明重复了就出队列
         * 目的就是保证队列的第一个元素出现的次数为1
         */
        while (!queue.isEmpty()&&arr[queue.peek()]>1){
            queue.poll();
        }
    }
    public Character get(){
        return queue.isEmpty()?'#':queue.peek();
    }

    public static void main(String[] args) {
        Stack05 stack05=new Stack05();
        stack05.insert('g');
        stack05.insert('o');
        stack05.insert('g');
        System.out.println(stack05.get());
    }
}
